Exact Decoding on Latent Variable Conditional Models is NP-Hard

摘要

Latent variable conditional models, including the latent conditional randomfields as a special case, are popular models for many natural languageprocessing and vision processing tasks. The computational complexity of theexact decoding/inference in latent conditional random fields is unclear. Inthis paper, we try to clarify the computational complexity of the exactdecoding. We analyze the complexity and demonstrate that it is an NP-hardproblem even on a sequential labeling setting. Furthermore, we propose thelatent-dynamic inference (LDI-Naive) method and its bounded version(LDI-Bounded), which are able to perform exact-inference oralmost-exact-inference by using top-$n$ search and dynamic programming.